In a cloud environment, the deployment of an application (workload) involves the allocation of resources in multiple domains. The most common domain is the domain of consumable resources, such as CPU cores, memory, and disk space. Traditionally, this domain has been the main factor in resource allocation problems. An application would specify its demand requirements for the various consumable resources, and a resource allocator, knowing the resources capacity and their current availability, allocates the required resources to the requesting application. In a cloud environment, in addition to consumable resource requirements, an application specifies other requirements and constraints. Consider, for example, an application (workload) which consists of a number of virtual machines and data volumes and services. Such Virtual Entities have resource requirements from their corresponding hosting Physical Entities, such as physical machines and storage devices. But, in addition, there may be some communications requirements among the logical entities, such as bandwidth and/or delay (requirements and constraints). Also, there may be location constraints specifying proximity of the LEs, for example an individual virtual machine (VM) to a data volume (DV) which holds the data processed by software running on that VM. Further, there might be availability and/or legal constraints for co-locating and antico-locating LEs in zones in the cloud infrastructure.
Current resource allocation schemes are typically concerned with only the allocation “domain” of placing of logical entities of the requested application on consumable physical resources. In case there are multiple domains, they are usually handled independently, making it hard, if not practically impossible, to best satisfy the requirements in all domains. Thus there is a need to dynamically introduce/alter a placement policy in a given allocation domain.
Further, cloud service providers need to accommodate an incoming stream of workload requests, each comprising a set of logical entities (LE), such as VMs and data volumes, and place them onto the cloud infrastructure which is a collection of physical entities (PE), such as physical machines (PMs) and storage devices (STGs). The workload request is encoded in some document defining the LEs, their resource requirements, as well as other constraints such as networking, affinity, licensing, multi-cloud, and cost. At the same time, the cloud provider has a multitude of objectives to satisfy, such efficiency of resource usage, quality-of-service, satisfy as much as possible users' requirements and constraints, and cost.
The problem is that the objectives/goals and related policies, for both cloud users and cloud service providers, are not necessarily fixed. Rather, they may change over time and may be revisited.
Devising a particular placement solution tailored to a given set of constraints and objectives may result in an inadequate management system.
A decade ago, researchers were concerned with placing individual virtual machines on physical machines. Requirements were simply stated as resource requirements. Such a placement problem is an instance of the bin packing problem (NP-hard). Several placement algorithms were designed to solve such problem efficiently. When a collection of virtual machines were considered as an application to be placed in the cloud, along with communication requirements among them, the problem became more complex, since the physical communication paths had to satisfy any virtual bandwidth requirements. Some heuristic optimization techniques were devised to solve such placement problem. However, adding location preference requirements, whereby one may specify a collocation (or anti-collocation) requirement at some level in the cloud hierarchical topology between a pair of virtual machines, makes the problem more complex.
While classes of solution algorithms exist that are based on clustering techniques, or based on reducing the size of the problem through analyzing the state of the cloud and identifying “cold spots” in the cloud that would be the domain of placement, such algorithms are usually designed given the constraints and objectives a priori. An optimization problem is formulated and a particular algorithm that suits the nature of the problem is sought.